Corelab Seminar
2015-2016
Vasilis Gkatzelis
Approximating the Nash Social Welfare with Indivisible Items
Abstract.
We study the problem of allocating a set of indivisible items among agents
with additive valuations with the goal of maximizing the geometric mean of
the agents’ valuations, i.e., the Nash social welfare. This problem is known
to be NP-hard, and our main result is the first efficient constant-factor
approximation algorithm for this objective. We first observe that the
integrality gap of the natural fractional relaxation is unbounded, so we
propose a different fractional allocation which implies a tighter upper
bound and, after appropriate rounding, yields a good integral allocation.
An interesting contribution of this work is the fractional allocation that
we use. The relaxation of our problem can be solved efficiently using the
Eisenberg-Gale program, whose optimal solution can be interpreted as a
market equilibrium with the dual variables playing the role of item prices.
Using this market-based interpretation, we define an alternative equilibrium
allocation where the amount of spending that can go into any given item is
bounded, thus keeping the highly priced items under-allocated, and forcing
the agents to spend on lower priced items. The resulting equilibrium
allocation reveals more information regarding how to assign items so as to
obtain a good integral allocation.
Joint work with Richard Cole; appeared in STOC 2015.